package leetcode.L500;

import java.util.Arrays;

public class EX322 {
    public static int coinChange(int[] coins, int amount) {
        Arrays.sort(coins);
        int res = 0;
        for(int i = coins.length-1 ; i >= 0 ; i--){
            res = res + (amount/coins[i]);
            amount = amount%coins[i];
            if(amount==0){
                break;
            }
        }
        if(amount!=0){
            return -1;
        }
        return res;

    }

    public static void main(String[] args) {
        int[] num = {186,419,83,408};
        coinChange(num,6249);
    }
}
